package com.yitau.sort;

import com.yitau.utils.ArrayUtils;

/**
 * 堆排序
 */
public class HeapSort {

    /**
     * 维护一个最大堆
     * @param array 数组
     * @param x 新节点，假定其左孩子和右孩子都为最大堆
     */
    public static void maxHeapify(int[] array, int size, int x) {
        // 找到 x 和其左右孩子中最大的
        int leftChild = 2 * x + 1;
        int rightChild = 2 * (x + 1);
        int largest = x;
        // leftChild 和 rightChild在数组有效长度内
        if (leftChild < size && array[leftChild] > array[x]) {
            largest = leftChild;
        }
        if (rightChild < size && array[rightChild] > array[largest]) {
            largest = rightChild;
        }
        // 如果最大的不是 x ，说明当前违背了最大堆的性质
        if (largest != x) {
            ArrayUtils.swap(array, x, largest);
            // 交换后，需要考虑子树是否会违背性质，递归调用
            maxHeapify(array, size, largest);
        }
    }

    /**
     * 通过数组 array 建立一个最大堆
     * 1. 最开始时数组array的每一个元素都是堆
     * 2. 可以证明，当数组长度为 n 时，叶节点下标分别为 n/2+1, n/2+2, ..., n
     * @param array 原数组
     */
    public static void buildMaxHeap(int[] array) {
        for (int i = array.length / 2; i >= 0; i--) {
            maxHeapify(array, array.length, i);
        }
    }

    /**
     * 1. 先创建一个最大堆数组（默认从小到大排序）Heap ，最大堆第一个元素最大
     * 2. 把堆首（最大值）和堆尾互换
     * 3. 把堆的 size 减 1，维护最大堆的性质
     * 4. 重复步骤 3 ，直到堆的 size 为 1
     * @param array 原数组，排序后改变内容
     */
    public static void heapSort(int[] array) {
        System.out.print("排序前：");
        ArrayUtils.printArray(array);
        // 首先将数组 array 建立成最大堆
        buildMaxHeap(array);
        int size = array.length;
        for (int i = array.length - 1; i > 0; i--) {
            // 将第一个元素（最大）与最后一个元素交换位置
            ArrayUtils.swap(array, 0, i);
            size--;
            maxHeapify(array, size, 0);
        }
        System.out.print("排序后：");
        ArrayUtils.printArray(array);
    }

    public static void main(String[] args) {
        // write your code here
        System.out.println("正序：");
        heapSort(ArrayUtils.DEFAULT_ARRAY_ASC);
        System.out.println("逆序：");
        heapSort(ArrayUtils.DEFAULT_ARRAY_DESC);
        System.out.println("随机：");
        heapSort(ArrayUtils.DEFAULT_ARRAY_RANDOM);
    }

}
